package com.lqian.simplestructure.linearlist.lru;

import java.util.HashMap;

public class LRUCacheTask {
 
    public static void main(String[] args) {
        LRUCacheTask cacheTask = new LRUCacheTask(2);
        cacheTask.put(1,1);
        cacheTask.put(2,2);
        int i = cacheTask.get(1);
        cacheTask.put(3,3);
    }
 
    private MyCache<Integer,Integer> cache;
 
    public LRUCacheTask(int capacity){
        cache = new MyCache<>(capacity);
    }
 
    public int get(int key){
        Integer ans = cache.get(key);
        return ans == null ? -1:ans;
    }
 
    public void put(int key ,int value){
        cache.set(key,value);
    }
 
    /**
     * 定义双向链表
     * @param <K>
     * @param <V>
     */
    public static class Node<K,V>{
        public K key;
        public V value;
        public Node next;
        public Node last;
 
        public Node(K key,V value){
            this.key = key;
            this.value = value;
        }
    }
 
    /**
     * 定义双向链表的API
     * @param <K>
     * @param <V>
     */
    public static class NodeDoubleLinkList<K,V>{
        private Node<K,V> head;
        private Node<K,V> tail;
 
        public NodeDoubleLinkList(){
            this.head = null;
            this.tail = null;
        }
 
        /**
         * 删除首节点
         */
        public  Node<K,V> removeHead(){
            if(head== null){
                return null;
            }
            Node<K,V> res = head;
            if(head == tail){
                head = null;
                tail = null;
            }else {
                head = res.next;
                res.next = null;
                head.last = null;
            }
            return res;
        }
 
        /**
         * 新增尾节点
         */
        public void addTail(Node<K,V> newNode){
            if(newNode == null){
                return;
            }
            if(head == null){
                head = newNode;
                tail = newNode;
            }else {
                tail.next = newNode;
                newNode.last = tail;
                tail = newNode;
            }
        }
 
        /**
         * 把某个节点移动到尾节点
         */
        public void moveToTail(Node<K,V> oldNode){
            if(tail == oldNode){
                return;
            }
            if(head == oldNode){
                head = oldNode.next;
                head.last = null;
            }else {
                oldNode.last.next = oldNode.next;
                oldNode.next.last = oldNode.last;
            }
            tail.next = oldNode;
            oldNode.last = tail;
            oldNode.next = null;
            tail = oldNode;
        }
    }
 
    /**
     * 缓存操作的核心方法
     * @param <K>
     * @param <V>
     */
    public static class MyCache<K,V>{
        private HashMap<K,Node<K,V>> keyNodeMap;
        private NodeDoubleLinkList<K,V> nodeList;
        private final int capacity;
 
 
        public MyCache(int capacity) {
            if(capacity < 1){
                throw new RuntimeException("capacity is must more than 0");
            }
            keyNodeMap = new HashMap<K,Node<K,V>>();
            nodeList = new NodeDoubleLinkList<K,V>();
            this.capacity = capacity;
        }
 
        public V get(K key){
            if(keyNodeMap.containsKey(key)){
                Node<K, V> kvNode = keyNodeMap.get(key);
                nodeList.moveToTail(kvNode);
                return kvNode.value;
            }
            return null;
        }

        public void set(K key,V value){
            if(keyNodeMap.containsKey(key)){
                Node<K, V> kvNode = keyNodeMap.get(key);
                kvNode.value = value;
                nodeList.moveToTail(kvNode);
            }else {
                if(keyNodeMap.size() == capacity){
                    removeMostUnusedCache();
                }
                Node<K,V> newNode = new Node<>(key, value);
                keyNodeMap.put(key,newNode);
                nodeList.addTail(newNode);
            }
        }
 
        /**
         * 删除不常用的数据
         */
        private void removeMostUnusedCache() {
            Node<K, V> kvNode = nodeList.removeHead();
            keyNodeMap.remove(kvNode.key);
        }
    }
 
}